#include <iostream>
using namespace std;
/*
 * @lc app=leetcode.cn id=5 lang=cpp
 *
 * [5] 最长回文子串
 */

// @lc code=start
class Solution {
public:
    string longestPalindrome(string s) {
        bool dp[1005][1005];
        for (int i = 0; i < s.size(); i++)
            dp[i][i] = true;
        int max_len = 1, start = 0;
        for (int j = 1; j < s.size(); j++) {
            for (int i = 0; i < j; i++) {
                if (s[i] != s[j]) dp[i][j] = false;
                if (s[i] == s[j]) {
                    if (j - i < 3) dp[i][j] = true;
                    else dp[i][j] = dp[i + 1][j - 1];
                }
                if (dp[i][j] && j - i + 1 > max_len) {
                    max_len = j - i + 1;
                    start = i;
                }
            }
        }
        return s.substr(start, max_len);
    }
};
// @lc code=end

